package Leetcode第一期;

import java.util.*;

/**
 * @author : K k
 * @date : 16:24 2020/9/10
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 说明：
 *
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 *
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 *   [1, 7],
 *   [1, 2, 5],
 *   [2, 6],
 *   [1, 1, 6]
 * ]
 * 示例 2:
 *
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 *   [1,2,2],
 *   [5]
 * ]
 *
 */
public class 组合总和_II_40 {

    List<List<Integer>> lists=new ArrayList<>();
    Deque<Integer> deque=new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int length=candidates.length;
        if (candidates.length==0){return lists;}

        //升序排序
        Arrays.sort(candidates);
        dfsSolver(candidates,length,0,target,deque);
        return lists;
    }



    //深度优先回溯
    private void dfsSolver(int[] candidates, int length, int start, int target, Deque<Integer> deque) {
        //若target为0 则找到了答案数组
        if (target==0){
            lists.add(new ArrayList<>(deque));
            return;
        }

        for (int i=start; i<length;i++){
            if (candidates[i]>target){break;}

            if (i>start && candidates[i]==candidates[i-1]){
                //重复项去除  前一个数 已经包括了后一个重复数的候选数
                continue;
            }
            deque.addLast(candidates[i]);
            dfsSolver(candidates,length,i+1,target-candidates[i],deque);
            deque.removeLast();
        }

    }
    public static void main(String[] args) {
        int[] candidates = new int[]{2,5,2,1,2};
        int target = 5;

        List<List<Integer>> res =new 组合总和_II_40().combinationSum2(candidates,target);
        System.out.println("输出 => " + res);
    }

}
